package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.Arrays;

/**
 * @author zhangjy
 * @description 从前序与中序遍历序列构造二叉树
 * @date 2025/4/22 11:54
 */
public class BuildTree_105 {

    public static void main(String[] args) {

    }

    /**
     * 个解：dfs-递归-前序（TODO 待完善，目前边界处理有误）；
     * <p>
     * 思路：
     * 复制数组耗费时间和空间，在原数组移动下标实现逻辑分割，从而减少物理分割的耗时、耗空间。
     */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        TreeNode node = dfs2(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
        return node;
    }

    public TreeNode dfs2(int[] preorder, int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
        if (preorderEnd > preorderStart) return null;

        // 分割中序基准
        int splitInorder = preorder[preorderStart];
        TreeNode node = new TreeNode(splitInorder);

        // 1.分割中序
        int pivotInorder = getIndex(inorder, splitInorder);
        // 左闭右闭（分割后的数组下标）
        int inorderLeftStart = inorderStart;
        int inorderLeftEnd = pivotInorder - 1;
        int inorderRightStart = pivotInorder + 1;
        int inorderRightEnd = inorderEnd;

        // 2.分割前序
        // 中序左的元素个数
        int pivotPreorder = inorderLeftEnd - inorderLeftStart + 1;
        // 前序的首位元素已经使用过，所以+1
        int preorderLeftStart = preorderStart + 1;
        int preorderLeftEnd = preorderLeftStart + pivotPreorder - 1;
        int preorderRightStart = pivotInorder + 1;
        int preorderRightEnd = preorderEnd;

        TreeNode leftChild = dfs2(preorder, inorder, preorderLeftStart, preorderLeftEnd, inorderLeftStart, inorderLeftEnd);
        TreeNode rightChild = dfs2(preorder, inorder, preorderRightStart, preorderRightEnd, inorderRightStart, inorderRightEnd);
        node.left = leftChild;
        node.right = rightChild;

        return node;
    }

    /**
     * 个解：dfs-递归；
     * <p>
     * 思路：
     * 切割数组；根据前切割中，再根据得到的中去切割前
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 两个数组大小一定相同
        if (preorder.length == 0) return null;

        // 1.分割中序
        // 分割中序基准
        int splitInorder = preorder[0];
        TreeNode node = new TreeNode(splitInorder);
        int pivotInorder = getIndex(inorder, splitInorder);
        // 分割中序
        // 左闭右开
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, pivotInorder);
        int[] inorderRight = Arrays.copyOfRange(inorder, pivotInorder + 1, inorder.length);
        // 2.分割前序
        // 分割前序基准
        int splitPreorder = inorderLeft.length;
        // 首位元素已经使用过，所以从1开始；左闭右开，要包含基准，所以+1
        int[] preorderLeft = Arrays.copyOfRange(preorder, 1, splitPreorder + 1);
        int[] preorderRight = Arrays.copyOfRange(preorder, splitPreorder + 1, preorder.length);

        // 3.递归
        TreeNode leftChild = buildTree(preorderLeft, inorderLeft);
        TreeNode rightChild = buildTree(preorderRight, inorderRight);

        node.left = leftChild;
        node.right = rightChild;

        return node;
    }

    public int getIndex(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }

}
